package g

/*
 * @lc app=leetcode.cn id=69 lang=golang
 *
 * [69] x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
*/

// @lc code=start
func mySqrt(x int) int {
	return mySqrt3(x)
}

func mySqrt1(x int) int {
	if x == 1 {
		return 1
	}
	for i := 1; i <= x; i++ {
		if i*i > x {
			return i - 1
		}
	}
	return 0
}

// 内存越界
func mySqrt2(x int) int {
	return mySqrtRecursion(x, 0, x)
}

func mySqrtRecursion(x, l, r int) int {
	if l*l >= x {
		return l
	}
	if r*r <= x {
		return r
	}
	mid := (r-l)/2 + l
	if mid*mid > x {
		r = mid
	} else {
		l = mid
	}
	return mySqrtRecursion(x, l, r)
}

func mySqrt3(x int) int {
	if x == 0 {
		return 0
	}
	if x == 1 {
		return 1
	}
	i := 1
	step := 5
	for ; i <= x; i += step {
		if i*i > x {
			break
		}
	}
	for j := i - step; j <= i; j++ {
		if j*j > x {
			return j - 1
		}
	}
	return 0
}

// @lc code=end
